package top.ivansong92.example.leetcode.learning.common.algorithms.recall;

import org.junit.Test;

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Collectors;

public class TestExample {

    /**
     * 17. 电话号码的字母组合
     *
     * @return
     */
    @Test
    public void testLetterCombinations() {
        System.out.println(String.join("|", letterCombinations("234")));
    }

    private static Map<Character, List<Character>> LETTER_MAP = new HashMap<>();

    static {
        LETTER_MAP.put('2', Arrays.asList('a', 'b', 'c'));
        LETTER_MAP.put('3', Arrays.asList('d', 'e', 'f'));
        LETTER_MAP.put('4', Arrays.asList('g', 'h', 'i'));
        LETTER_MAP.put('5', Arrays.asList('j', 'k', 'l'));
        LETTER_MAP.put('6', Arrays.asList('m', 'n', 'o'));
        LETTER_MAP.put('7', Arrays.asList('p', 'q', 'r', 's'));
        LETTER_MAP.put('8', Arrays.asList('t', 'u', 'v'));
        LETTER_MAP.put('9', Arrays.asList('w', 'x', 'y', 'z'));

    }

    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return Collections.emptyList();
        }
        List<String> res = new ArrayList<>();
        doCombine(res, digits, "", 0);
        return res;
    }

    private void doCombine(List<String> res, String digits, String parent, int index) {
        if (index == digits.length()) {
            res.add(parent);
            return;
        }

        List<Character> letters = LETTER_MAP.get(digits.charAt(index));
        if (letters == null || letters.size() == 0) {
            return;
        }

        int next = index + 1;
        for (Character ch : letters) {
            doCombine(res, digits, parent + ch.toString(), next);
        }
    }


    @Test
    public void testRestoreIpAddresses() {
        System.out.println(String.join("|", restoreIpAddresses("25525511135")));
    }

    /**
     * 93. 复原 IP 地址
     *
     * @param s
     * @return
     */
    public List<String> restoreIpAddresses(String s) {
        if (s == null || s.length() < 4 || s.length() > 12) {
            return Collections.emptyList();
        }

        List<String> res = new ArrayList<>();

        doRestoreIp(s, 0, res, new ArrayList<>());

        return res;
    }

    private void doRestoreIp(String s, int start, List<String> res, List<String> parent) {
        if (parent.size() == 3) {
            if (start == s.length()) {
                return;
            }

            String subS = s.substring(start);
            if (matchIpSub(subS)) {
                List<String> newPath = new ArrayList<>(parent);
                newPath.add(subS);
                res.add(String.join(".", newPath));
            }
            return;
        }
        List<String> newPath;
        for (int i = start + 1; i <= s.length() - 1 && i <= start + 3; i++) {
            String val = s.substring(start, i);
            if (matchIpSub(val)) {
                newPath = new ArrayList<>(parent);
                newPath.add(val);
                doRestoreIp(s, i, res, newPath);
            }
        }
    }

    private boolean matchIpSub(String val) {
        if (val == null) {
            return false;
        }

        int len = val.length();
        if (len == 2 || len == 3) {
            if (val.startsWith("0")) {
                return false;
            }
            int intVal = Integer.parseInt(val);
            return intVal <= 255;
        } else {
            return len == 1;
        }
    }


    @Test
    public void testPartition() {
        System.out.println(String.join("|", partition("abb").stream().map(list -> String.join(",", list)).collect(Collectors.toList())));
    }


    /**
     * 131. 分割回文串
     *
     * @param s
     * @return
     */
    public List<List<String>> partition(String s) {
        if (s == null || s.length() == 0) {
            return Collections.emptyList();
        }
        List<List<String>> res = new ArrayList<>();
        doPartition(s, 0, new ArrayList<>(), res);
        return res;
    }

    private void doPartition(String s, int start, List<String> list, List<List<String>> res) {
        if (start == s.length()) {
            res.add(list);
            return;
        }
        List<String> newList;
        for (int i = start + 1; i <= s.length(); i++) {
            String sub = s.substring(start, i);
            if (match(sub)) {
                newList = new ArrayList<>(list);
                newList.add(sub);
                doPartition(s, i, newList, res);
            }
        }
    }

    private boolean match(String s) {
        if (s == null || s.length() == 0) {
            return false;
        }

        int len = s.length();
        if (len > 1) {
            int start = 0, end = len - 1;
            while (start <= end) {
                if (s.charAt(start) != s.charAt(end)) {
                    return false;
                }
                start++;
                end--;
            }
        }
        return true;
    }


    /**
     * 46. 全排列
     */
    public List<List<Integer>> permute(int[] nums) {
        if (nums == null || nums.length == 0) {
            return Collections.emptyList();
        }
        List<List<Integer>> result = new ArrayList<>();
        boolean[] pathTag = new boolean[nums.length];
        trace(result, new ArrayList<>(), pathTag, nums);
        return result;
    }

    private void trace(List<List<Integer>> result, List<Integer> array, boolean[] pathTag, int[] nums) {
        if (array.size() == nums.length) {
            result.add(new ArrayList<>(array));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (pathTag[i]) {
                continue;
            }
            pathTag[i] = true;
            array.add(nums[i]);
            trace(result, array, pathTag, nums);
            array.remove(array.size() - 1);
            pathTag[i] = false;
        }
    }

    /**
     * 47. 全排列 II
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> permuteUnique(int[] nums) {
        if (nums == null || nums.length == 0) {
            return Collections.emptyList();
        }

        if (nums.length == 1) {
            return Collections.singletonList(Collections.singletonList(nums[0]));
        }

        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        doPermuteSearch(nums, new ArrayList<>(), new boolean[nums.length], res);
        return res;
    }

    private void doPermuteSearch(int[] nums, List<Integer> path, boolean[] usered, List<List<Integer>> res) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (usered[i]) {
                continue;
            }

            if (i > 0 && nums[i] == nums[i - 1] && usered[i - 1]) {
                continue;
            }
            usered[i] = true;
            path.add(nums[i]);
            doPermuteSearch(nums, path, usered, res);
            path.remove(path.size() - 1);
            usered[i] = false;
        }
    }


    /**
     * 77.组合
     *
     * @param n
     * @param k
     * @return
     */
    public List<List<Integer>> combine(int n, int k) {
        if (k > n || n < 1) {
            return Collections.emptyList();
        }

        int[] nums = new int[n];
        for (int i = 1; i <= n; i++) {
            nums[i - 1] = i;
        }

        List<List<Integer>> result = new ArrayList<>();
        trace(result, new ArrayList<>(), new boolean[nums.length], nums, k, 0);

        return result;
    }

    private void trace(List<List<Integer>> result, List<Integer> array, boolean[] pathTag, int[] nums, int limit, int start) {
        if (array.size() == limit) {
            result.add(new ArrayList<>(array));
            return;
        }
        for (int i = start; i < nums.length; i++) {
            if (pathTag[i]) {
                continue;
            }
            pathTag[i] = true;
            array.add(nums[i]);
            trace(result, array, pathTag, nums, limit, i + 1);
            array.remove(array.size() - 1);
            pathTag[i] = false;
        }
    }


    public List<List<Integer>> combineV2(int n, int k) {
        if (k > n || n < 1) {
            return Collections.emptyList();
        }

        List<List<Integer>> result = new ArrayList<>();
        genCombineList(result, new ArrayList<>(), k, n, 1);

        return result;
    }

    private void genCombineList(List<List<Integer>> result, List<Integer> array, int k, int n, int start) {
        if (array.size() == k) {
            result.add(new ArrayList<>(array));
            return;
        }
        int size = array.size();

        for (int i = start; i <= n - (k - size) + 1; i++) {
            array.add(i);
            genCombineList(result, array, k, n, i + 1);
            array.remove(array.size() - 1);
        }
    }


    @Test
    public void testCombinationSum() {
        System.out.println(String.join("|", combinationSum(new int[]{2, 3, 6, 7}, 7).stream().map(list -> Arrays.toString(list.toArray())).collect(Collectors.toList())));
    }

    /**
     * 39. 组合总和
     *
     * @param candidates
     * @param target
     * @return
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if (candidates == null || candidates.length == 0) {
            return Collections.emptyList();
        }
        int len = candidates.length;
        if (len == 1) {
            int elem = candidates[0];
            if (elem > target) {
                return Collections.emptyList();
            } else if (elem == target) {
                return Collections.singletonList(Collections.singletonList(elem));
            } else if (target % elem != 0) {
                return Collections.emptyList();
            } else {
                int num = target / elem;
                List<Integer> list = new ArrayList<>();
                for (int i = 0; i < num; i++) {
                    list.add(elem);
                }
                return Collections.singletonList(list);
            }
        }
        Arrays.sort(candidates);
        if (candidates[0] > target) {
            return Collections.emptyList();
        }
        List<List<Integer>> res = new ArrayList<>();
        doFindCombinationSum(null, 0, candidates, target, new ArrayList<>(), res);
        return res;
    }

    private void doFindCombinationSum(Integer parentVal, int start, int[] array, int target, List<Integer> list, List<List<Integer>> res) {
        if (parentVal != null && parentVal > target) {
            return;
        } else if (parentVal != null && parentVal == target) {
            res.add(new ArrayList<>(list));
            return;
        }

        int pVal = parentVal == null ? 0 : parentVal;
        for (int i = start; i < array.length; i++) {
            int ele = array[i];
            int newParent = pVal + ele;
            if (newParent > target) {
                break;
            }

            list.add(ele);
            doFindCombinationSum(newParent, i, array, target, list, res);
            list.remove(list.size() - 1);
        }
    }


    @Test
    public void testCombinationSum2() {
        System.out.println(String.join("|", combinationSum2(new int[]{2, 5, 2, 1, 2, 1, 1, 2, 3, 1, 1, 1}, 6).stream().map(list -> Arrays.toString(list.toArray())).collect(Collectors.toList())));
    }

    /**
     * 40. 组合总和 II
     *
     * @param candidates
     * @param target
     * @return
     */
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        if (candidates == null || candidates.length == 0) {
            return Collections.emptyList();
        }

        int len = candidates.length;
        if (len == 1) {
            int elem = candidates[0];
            if (elem != target) {
                return Collections.emptyList();
            } else {
                return Collections.singletonList(Collections.singletonList(elem));
            }
        }
        Arrays.sort(candidates);
        if (candidates[0] > target) {
            return Collections.emptyList();
        }
        List<List<Integer>> res = new ArrayList<>();

        doFindCombinationSum2(0, 0, target, candidates, new ArrayList<>(), res);
        return res;
    }

    private void doFindCombinationSum2(int start, int parentVal, int target, int[] array, List<Integer> list, List<List<Integer>> res) {
        if (parentVal == target) {
            res.add(new ArrayList<>(list));
            return;
        } else if (parentVal > target) {
            return;
        }
        for (int i = start; i < array.length; i++) {
            int val = array[i];
            if (i > start && val == array[i - 1]) {
                continue;
            }

            int newVal = val + parentVal;
            if (newVal > target) {
                break;
            }

            list.add(val);
            doFindCombinationSum2(i + 1, newVal, target, array, list, res);
            list.remove(list.size() - 1);
        }
    }


    @Test
    public void testCombinationSum3() {
        System.out.println(String.join("|", combinationSum3(3, 7).stream().map(list -> Arrays.toString(list.toArray())).collect(Collectors.toList())));
    }

    /**
     * 216. 组合总和 III
     *
     * @param k
     * @param n
     * @return
     */
    public List<List<Integer>> combinationSum3(int k, int n) {
        if (n < 1 || k < 1 || k > 9 || n > 45) {
            return Collections.emptyList();
        }

        if (k == 1) {
            if (n > 9) {
                return Collections.emptyList();
            } else {
                return Collections.singletonList(Collections.singletonList(n));
            }
        }

        List<List<Integer>> res = new ArrayList<>();
        doFindCombinationSum3(0, 1, n, k, new ArrayList<>(), res);
        return res;
    }

    private void doFindCombinationSum3(int parentVal, int start, int n, int k, List<Integer> list, List<List<Integer>> res) {
        if (parentVal == n && list.size() == k) {
            res.add(new ArrayList<>(list));
            return;
        } else if (list.size() >= k || parentVal >= n) {
            return;
        }

        for (int i = start; i <= 9; i++) {
            int newVal = parentVal + i;
            if (newVal > n) {
                break;
            }

            list.add(i);
            doFindCombinationSum3(newVal, i + 1, n, k, list, res);
            list.remove(list.size() - 1);
        }
    }

    /**
     * 78. 子集
     */
    public List<List<Integer>> subsets(int[] nums) {
        if (nums == null || nums.length == 0) {
            return Collections.emptyList();
        }

        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>());

        int len = nums.length;
        for (int i = 1; i <= len; i++) {
            doFindSubSets(nums, 0, i, new ArrayList<>(), res);
        }
        return res;
    }

    private void doFindSubSets(int[] nums, int start, int limit, List<Integer> list, List<List<Integer>> res) {
        if (list.size() == limit) {
            res.add(new ArrayList<>(list));
            return;
        }
        int end = nums.length - (limit - list.size()) + 1;
        for (int i = start; i < end; i++) {
            list.add(nums[i]);
            doFindSubSets(nums, i + 1, limit, list, res);
            list.remove(list.size() - 1);
        }
    }

    /**
     * 90. 子集 II
     * @param nums
     * @return
     */
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        if (nums == null || nums.length == 0) {
            return Collections.emptyList();
        }
        Arrays.sort(nums);

        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>());
        int len = nums.length;

        for (int i = 1; i <= len; i++) {
            doFindSubsetsWithDup(nums, 0, i, new ArrayList<>(), res);
        }
        return res;
    }

    private void doFindSubsetsWithDup(int[] nums, int start, int limit, List<Integer> list, List<List<Integer>> res) {
        if (list.size() == limit) {
            res.add(new ArrayList<>(list));
            return;
        }
        int end = nums.length - (limit - list.size()) + 1;
        for (int i = start; i < end; i++) {
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            list.add(nums[i]);
            doFindSubsetsWithDup(nums, i + 1, limit, list, res);
            list.remove(list.size() - 1);
        }
    }

    /**
     * 401. 二进制手表
     * @param turnedOn
     * @return
     */
    public List<String> readBinaryWatch(int turnedOn) {
        if (turnedOn < 0 || turnedOn > 8) {
            return Collections.emptyList();
        }

        if (turnedOn == 0) {
            return Collections.singletonList("0:00");
        }

        List<String> res = new ArrayList<>();

        int[] hourNO = new int[]{1, 2, 4, 8};
        int[] minuteNO = new int[]{1, 2, 4, 8, 16, 32};
        List<Integer> hourList, minuteList;
        for (int i = 0; i <= Math.min(turnedOn, 3); i++) {
            hourList = new ArrayList<>();
            doFindClock(0, 11, hourNO, 0, i, new ArrayList<>(), hourList);
            minuteList = new ArrayList<>();
            doFindClock(0, 59, minuteNO, 0, turnedOn - i, new ArrayList<>(), minuteList);
            for (Integer hour : hourList) {
                String pre = hour + ":";
                res.addAll(minuteList.stream().map(e -> {
                    if (e < 10) {
                        return pre + "0" + e;
                    }
                    return pre + e;
                }).collect(Collectors.toList()));
            }
        }

        return res;
    }

    private void doFindClock(int parentVal, int max, int[] nums, int start, int limit, List<Integer> list, List<Integer> clockList) {
        if (list.size() == limit && parentVal <= max) {
            clockList.add(parentVal);
            return;
        } else if (list.size() > limit || parentVal > max) {
            return;
        }

        int end = nums.length - (limit - list.size()) + 1;
        for (int i = start; i < end; i++) {
            int newVal = nums[i] + parentVal;
            if (newVal > max) {
                break;
            }

            list.add(newVal);
            doFindClock(newVal, max, nums, i + 1, limit, list, clockList);
            list.remove(list.size() - 1);
        }
    }


    /**
     * 79. 单词搜索
     * @param board
     * @param word
     * @return
     */

    public boolean exist(char[][] board, String word) {
        if (word == null || word.length() == 0 || board == null || board.length == 0) {
            return false;
        }

        int m = board.length;
        int n = board[0].length;
        int len = word.length();
        if (m * n < len) {
            return false;
        }

        boolean[][] used = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matchWord(board, i, j, m, n, used, word, 0, len)) {
                    return true;
                }
            }
        }
        return false;
    }

    private static int[][] DIRECT_MOVE_ARRAY = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    private boolean matchWord(char[][] wordArray, int x, int y, int maxX, int maxY, boolean[][] used, String word, int index, int wordLen) {

        if (wordLen == index || word.charAt(index) != wordArray[x][y]) {
            return false;
        }

        if (wordLen == index + 1) {
            return true;
        }

        int newIndex = index + 1;
        used[x][y] = true;
        for (int[] array : DIRECT_MOVE_ARRAY) {
            int newX = x + array[0];
            int newY = y + array[1];
            if (newX < 0 || newX >= maxX || newY < 0 || newY >= maxY || used[newX][newY]) {
                continue;
            }

            if (matchWord(wordArray, newX, newY, maxX, maxY, used, word, newIndex, wordLen)) {
                return true;
            }
        }
        used[x][y] = false;
        return false;
    }


    /**
     * 200. 岛屿数量
     * @param grid
     * @return
     */
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }


        int m = grid.length;
        int n = grid[0].length;

        boolean[][] used = new boolean[m][n];
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!used[i][j] && grid[i][j] == '1') {
                    res++;
                    dfs(grid, i, j, m, n, used);
                }
            }
        }
        return res;
    }

    private void dfs(char[][] grid, int x, int y, int maxX, int maxY, boolean[][] used) {
        used[x][y] = true;
        for (int[] array : DIRECT_MOVE) {
            int newX = x + array[0];
            int newY = y + array[1];
            if (newX < 0 || newX >= maxX || newY < 0 || newY >= maxY || used[newX][newY] || grid[newX][newY] == '0') {
                continue;
            }
            dfs(grid, newX, newY, maxX, maxY, used);
        }
    }

    /**
     * 130. 被围绕的区域
     * @param board
     */

    public void solve(char[][] board) {
        if (board == null || board.length == 0) {
            return;
        }
        int m = board.length;
        int n = board[0].length;

        boolean[][] used = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!used[i][j] && board[i][j] == '0') {
                    dfsBoard(board, i, j, m, n, used);
                }
            }
        }
    }

    private void dfsBoard(char[][] board, int x, int y, int maxX, int maxY, boolean[][] used) {
        used[x][y] = true;
        for (int[] array : DIRECT_MOVE) {
            int newX = x + array[0];
            int newY = y + array[1];
            if (newX < 0 || newX >= maxX || newY < 0 || newY >= maxY || used[newX][newY]) {
                continue;
            }

            if (board[newX][newY] == '0') {
                used[newX][newY] = true;
            } else {
                dfs(board, newX, newY, maxX, maxY, used);
            }
        }
    }

    /**
     * 417. 太平洋大西洋水流问题
     * @param heights
     * @return
     */
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        if (heights == null || heights.length == 0) {
            return Collections.emptyList();
        }
        List<List<Integer>> res = new ArrayList<>();
        int m = heights.length;
        int n = heights[0].length;

        if (m == 1) {
            for (int j = 0; j < n; j++) {
                res.add(Arrays.asList(0, j));
            }
            return res;
        } else if (n == 1) {
            for (int i = 0; i < m; i++) {
                res.add(Arrays.asList(i, 0));
            }
            return res;
        }

        boolean[][] pacificVisited = new boolean[m][n];
        boolean[][] atlanticVisited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            dsfHeights(heights, i, 0, heights[i][0], pacificVisited, m, n);
            dsfHeights(heights, i, n - 1, heights[i][n - 1], atlanticVisited, m, n);
        }

        for (int j = 0; j < n; j++) {
            dsfHeights(heights, 0, j, heights[0][j], pacificVisited, m, n);
            dsfHeights(heights, m - 1, j, heights[m - 1][j], atlanticVisited, m, n);
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacificVisited[i][j] && atlanticVisited[i][j]) {
                    res.add(Arrays.asList(i, j));
                }
            }
        }
        return res;
    }

    private static int[][] DIRECT_MOVE = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    private void dsfHeights(int[][] heights, int x, int y, int parentVal, boolean[][] visited, int maxX, int maxY) {
        int val = heights[x][y];
        if (val < parentVal) {
            return;
        }

        visited[x][y] = true;
        for (int[] array : DIRECT_MOVE) {
            int newX = x + array[0];
            int newY = y + array[1];
            if (newX < 0 || newX >= maxX || newY < 0 || newY >= maxY || visited[newX][newY]) {
                continue;
            }
            dsfHeights(heights, newX, newY, val, visited, maxX, maxY);
        }
    }


    /**
     * 51. N 皇后
     * @param n
     * @return
     */
    public List<List<String>> solveNQueens(int n) {
        if (n <= 0) {
            return Collections.emptyList();
        }

        if (n == 1) {
            return Collections.singletonList(Collections.singletonList("Q"));
        }
        List<List<String>> res = new ArrayList<>();
        doSolveNQueens(0, n, res, new ArrayList<>(), new boolean[n], new boolean[2 * n - 1], new boolean[2 * n - 1]);
        return res;
    }

    private void doSolveNQueens(int index, int n, List<List<String>> res, List<Integer> pos, boolean[] row, boolean[] dt1, boolean[] dt2) {
        if (index == n) {
            res.add(convertToNQString(pos));
            return;
        }

        int nextIndex = index + 1;
        for (int i = 0; i < n; i++) {
            int idx1 = index + i, idx2 = index - i + n - 1;
            if (row[i] || dt1[idx1] || dt2[idx2]) {
                continue;
            }
            row[i] = true;
            dt1[idx1] = true;
            dt2[idx2] = true;
            pos.add(i);
            doSolveNQueens(nextIndex, n, res, pos, row, dt1, dt2);
            row[i] = false;
            dt1[idx1] = false;
            dt2[idx2] = false;
            pos.remove(pos.size() - 1);
        }
    }

    private List<String> convertToNQString(List<Integer> pos) {
        List<String> res = new ArrayList<>();
        int len = pos.size();

        for (int val : pos) {
            StringBuilder string = new StringBuilder();
            for (int j = 0; j < len; j++) {
                if (j == val) {
                    string.append("Q");
                } else {
                    string.append(".");
                }
            }
            res.add(string.toString());
        }
        return res;
    }

    @Test
    public void testEraseOverlapIntervals() {
        System.out.println(eraseOverlapIntervals(new int[][]{{1,2}, {2,4}, {1,4}}));
    }

    /**
     * 435. 无重叠区间
     * @param intervals
     * @return
     */
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return 0;
        }
        int len = intervals.length;
        if (len == 1) {
            return 1;
        }

        Object[] objArray = Arrays.stream(intervals)
                .sorted((e1, e2) -> {
                    if (e1[0] != e2[0]) {
                        return e1[0] - e2[0];
                    }
                    return e1[1] - e2[1];
                }).toArray();
        for(int i = 0; i < len; i ++) {
            intervals[i] = (int[]) objArray[i];
        }
        Integer[] array = new Integer[len];
        int res = 0;
        for(int i = 0; i < len; i ++) {
            res = Math.max(res, 1 + doGetMaxEraseOverlap(intervals, i, len, array));
        }

        return len - res;
    }


    private int doGetMaxEraseOverlap(int[][] intervals, int index, int maxIndex, Integer[] array) {
        if (index >= maxIndex) {
            return 0;
        }

        Integer val = array[index];
        if (val != null) {
            return val;
        }
        int res = 0;
        int[] a1 = intervals[index];
        for(int i = index + 1; i < maxIndex; i ++) {
            if (hasContact(intervals[i], a1)) {
                continue;
            }
            res = Math.max(res, 1 + doGetMaxEraseOverlap(intervals, i, maxIndex, array));
        }
        array[index] = res;
        return res;
    }

    private boolean hasContact(int[] a1, int [] a2) {
        return (a1[0] > a2[0] && a1[0] < a2[1]) || (a2[0] > a1[0] && a2[0] < a1[1]) || (a1[0] == a2[0]);
    }


    /**
     * 60. 排列序列
     * @param n
     * @param k
     * @return
     */
    public String getPermutation(int n, int k) {
        if (n == 1) {
            return "1";
        }
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = i + 1;
        }
        List<String> res = new ArrayList<>();
        dsf(array, new boolean[n], new ArrayList<>(), new AtomicInteger(1), k, res);
        return res.get(0);
    }

    private void dsf(int[] nums, boolean[] flag, List<Integer> parent, AtomicInteger counter, int total, List<String> res) {
        if (parent.size() == nums.length) {
            int val = counter.incrementAndGet();
            if (val == total) {
                res.add(parent.stream().map(Object::toString).collect(Collectors.joining("")));
            }
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (flag[i]) {
                continue;
            }

            flag[i] = true;
            parent.add(nums[i]);
            dsf(nums, flag, parent, counter, total, res);
            if (!res.isEmpty()) {
                break;
            }
            flag[i] = false;
            parent.remove(parent.size() - 1);
        }
    }

    /**
     * 377. 组合总和 Ⅳ
     * @param nums
     * @param target
     * @return
     */
    public int combinationSum4(int[] nums, int target) {
        if (nums == null || nums.length == 0 || target <= 0) {
            return 0;
        }

        Arrays.sort(nums);
        if (nums[0] > target) {
            return 0;
        }
        Integer[] array = new Integer[target + 1];
        array[0] = 1;
        return  doCombinationSum4(nums, target, array);
    }

    private int doCombinationSum4(int[] nums, int target, Integer[] array) {
        Integer res = array[target];
        if (res != null) {
            return res;
        }
        res = 0;
        for (int i = 0; i < nums.length; i++) {
            int val = nums[i];
            if (val > target) {
                break;
            }
            res += doCombinationSum4(nums, target - val, array);
        }
        array[target] = res;
        return  res;
    }

    /**
     * 面试题 08.09. 括号
     * @param n
     * @return
     */
    public List<String> generateParenthesis(int n) {
        if (n <= 0) {
            return Collections.emptyList();
        }

        if (n == 1) {
            return Collections.singletonList("()");
        }
        List<String> res = new ArrayList<>();
        dfsParenthesis(n, n, "", res);
        return res;
    }
    private void dfsParenthesis(int left, int right, String string, List<String> list) {
        if (left == 0 && right == 0) {
            list.add(string);
            return;
        }

        if (left > 0) {
            dfsParenthesis(left - 1, right, string + "(", list);
        }

        if (left < right) {
            dfsParenthesis(left, right - 1, string + ")", list);
        }
    }

    @Test
    public void testNumEnclaves() {
        System.out.println(numEnclaves(new int[][]{{0,0,0,0},{1,0,1,0},{0,1,1,0},{0,0,0,0}}));
    }

    /**
     * 1020. 飞地的数量
     * @param grid
     * @return
     */
    public int numEnclaves(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int n = grid.length;
        int m = grid[0].length;
        if (n <= 2 || m <= 2) {
            return 0;
        }

        boolean[][] visited = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            dfsEnclave(grid, i, 0, n, m, visited);
            dfsEnclave(grid, i, m - 1, n, m, visited);
        }

        for (int j = 0; j < m; j++) {
            dfsEnclave(grid, 0, j, n, m, visited);
            dfsEnclave(grid, n - 1, j, n, m, visited);
        }
        int res = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    res++;
                }
            }
        }
        return res;
    }

    private static int[][] MOVE_ARRAY = new int[][]{{0, 1}, {-1, 0}, {0, -1}, {1, 0}};

    private void dfsEnclave(int[][] grid, int x, int y, int maxX, int maxY, boolean[][] visited) {
        if (grid[x][y] == 0) {
            return;
        }
        visited[x][y] = true;
        for (int[] array : MOVE_ARRAY) {
            int newX = array[0] + x;
            if (newX < 0 || newX >= maxX) {
                continue;
            }
            int newY = array[1] + y;
            if (newY < 0 || newY >= maxY) {
                continue;
            }

            if (visited[newX][newY] || grid[newX][newY] == 0) {
                continue;
            }
            visited[newX][newY] = true;
            dfsEnclave(grid, newX, newY, maxX, maxY, visited);
        }
    }

    @Test
    public void testSubarraysDivByK() {
        System.out.println(subarraysDivByK(new int[]{4, 5, 0, -2, -3, 1}, 5));
    }

    public int subarraysDivByK(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int len = nums.length;
        if (len == 1) {
            return nums[0] % k == 0 ? 1 : 0;
        }

        int res = 0;
        for(int i = 0; i < len; i ++) {
            int val = nums[i];
            if (val % k == 0) {
                res ++;
            }
            for(int j = i + 1; j < len; j ++) {
                val += nums[j];
                if (val % k == 0) {
                    res ++;
                }
            }
        }
        return res;
    }

    @Test
    public void testFindDiagonalOrder() {
        System.out.println(findDiagonalOrder(new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}));
    }

    /**
     * 498. 对角线遍历
     * @param mat
     * @return
     */
    public int[] findDiagonalOrder(int[][] mat) {
        if (mat == null || mat.length == 0) {
            return new int[0];
        }

        int m = mat.length;
        if (m == 1) {
            return mat[0];
        }

        int n = mat[0].length;
        if (n == 0) {
            return new int[0];
        }

        if (n == 1) {
            int[] res = new int[m];
            for(int i = 0; i < m; i ++) {
                res[i] = mat[i][0];
            }
            return res;
        }
        int[] res = new int[m * n];
        int x = 0, y = 0, index = 0;
        boolean up = true;

        while (index < res.length) {
            res[index ++] = mat[x][y];
            if (up) {
                if (x == 0 || y == n - 1) {
                    up = false;
                    if (y == n - 1) {
                        x = x + 1;
                    } else {
                        y = y + 1;
                    }
                } else {
                    x = x - 1;
                    y = y + 1;
                }
            } else {
                if (y == 0 || x == m - 1) {
                    up = true;
                    if (x == (m - 1)) {
                        y = y + 1;
                    } else {
                        x = x + 1;
                    }
                } else {
                    x = x + 1;
                    y = y - 1;
                }
            }
        }
        return res;
    }
}